/*
The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.
There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.
What 12-digit number do you form by concatenating the three terms in this sequence?

Anser:296962999629
Time:187ns
*/
package main

import (
	"fmt"
	"time"
)

func main() {
	t := time.Now()
	defer fmt.Println(time.Since(t))
	// start here
	l := 10000
	s := genPrime(l)
	for i := l / 10; i < l; i++ {
		if !s[i] {
			for j := i + 1; j < l; j++ {
				if !s[j] && isPermutation(i, j) {
					k := 2*j - i
					if k < l && !s[k] && isPermutation(i, k) {
						fmt.Printf("%d%d%d\n", i, j, k)
					}
				}
			}
		}
	}
}

func genPrime(l int) []bool {
	s := make([]bool, l)
	for i := 2; i < l; i++ {
		if !s[i] {
			for j := 2; i*j < l; j++ {
				s[i*j] = true
			}
		}
	}
	return s
}

func isPermutation(n1, n2 int) bool {
	m := make(map[int]int, 8)
	for n1 > 0 {
		m[n1%10]++
		n1 /= 10
	}
	for n2 > 0 {
		m[n2%10]--
		n2 /= 10
	}
	for _, v := range m {
		if v != 0 {
			return false
		}
	}
	return true
}
